/**
 * 同余原理：处理中间过程数值溢出的情况
 */
public class CongruenceTheorem {

    public static void main(String[] args) {
//        System.out.println(superPalindromesInRange("1", "1000000000000000000"));
        System.out.println(superPalindromesInRange("4", "1000"));
    }

    public static int superPalindromesInRange(String left, String right) {
        long l = Long.parseLong(left);
        long r = Long.parseLong(right);

        long sqrtR = (long) Math.sqrt(r);
        long num = 0;
        int count = 0;
        long seed = 1;
        while (num <= sqrtR) {
            num = evenLarge(seed);
            if (check(num * num, l, r)) {
                count++;
                System.out.println(num * num);
            }
            num = oddLarge(seed);
            if (check(num * num, l, r)) {
                count++;
                System.out.println(num * num);
            }
            seed++;
        }
        return count;
    }

    private static long oddLarge(long seed) {
        if (seed < 10) {
            return seed;
        }
        String right = new StringBuilder(seed / 10 + "").reverse().toString();
        return Long.parseLong(String.valueOf(seed).concat(right));
    }

    private static boolean check(long num, long l, long r) {
        String reversed = new StringBuilder(num + "").reverse().toString();
        return String.valueOf(num).equals(reversed) && l <= num && r >= num;
    }

    public static long evenLarge(long seed) {
        String reversed = new StringBuilder(seed + "").reverse().toString();
        return Long.parseLong(String.valueOf(seed).concat(reversed));
    }


}
